package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC93 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> res = new ArrayList<>();
            if (null == s) return res;
            StringBuilder curRes = new StringBuilder();
            restoreIpAddressesRecur(s, 0, s.length() - 1, 4, res, curRes);
            return res;
        }

        public void restoreIpAddressesRecur(String s, int start, int end, int depth, List<String> res, StringBuilder curRes) {
            if (null == s || depth < 0 || (depth > 0 && start > end) ||
                    ((end - start + 1) < depth && (end - start + 1) > depth * 3)) return;

            if (depth == 1 && start <= end) {
                if (end - start <= 2 && curSegmentValid(s, start, end, end - start + 1)
                        && !(end - start >= 1 && s.charAt(start) == '0')) {
                    String ip = curRes.toString() + s.substring(start, end + 1);
                    res.add(ip);
                }
                return;
            }

            // choose 1 bit
            if (start <= end && curSegmentValid(s, start, end, 1)) {
                curRes.append(String.valueOf(s.charAt(start)) + ".");
                restoreIpAddressesRecur(s, start + 1, end, depth - 1, res, curRes);
                curRes.delete(curRes.length() - 2, curRes.length());
            }

            // choose 2 bit
            if (start + 1 <= end && curSegmentValid(s, start, end, 2) && s.charAt(start) != '0') {
                curRes.append(String.valueOf(s.charAt(start)) + String.valueOf(s.charAt(start + 1)) + ".");
                restoreIpAddressesRecur(s, start + 2, end, depth - 1, res, curRes);
                curRes.delete(curRes.length() - 3, curRes.length());
            }

            // choose 3 bit
            if (start + 2 <= end && curSegmentValid(s, start, end, 3) && s.charAt(start) != '0') {
                curRes.append(String.valueOf(s.charAt(start)) + String.valueOf(s.charAt(start + 1)) + String.valueOf(s.charAt(start + 2)) + ".");
                restoreIpAddressesRecur(s, start + 3, end, depth - 1, res, curRes);
                curRes.delete(curRes.length() - 4, curRes.length());
            }
            return;
        }

        public boolean curSegmentValid(String s, int start, int end, int chooseBit) {
            if (end - start <= 1) return true;
            if (s.charAt(start) == '0' || s.charAt(start) == '1' ||
                    (s.charAt(start) == '2' && chooseBit == 3 && Integer.parseInt(s.substring(start, start + 3)) <= 255))
                return true;
            if (chooseBit <= 2) return true;
            return false;
        }
    }

    public void run() {
        Solution solution = new Solution();
        String s = "010010";
        System.out.println(solution.restoreIpAddresses(s));
    }

    public static void main(String[] args) throws Exception {
        LC93 an = new LC93();
        an.run();

//        System.out.println('1'<='5');
        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
